package main

import "fmt"

func main() {
	arr := []int{1, 2, 3, 4, 5}
	tree := build(arr)
	tree.upDate(0, 3, 10) //arr[0, 3]区间加10
	fmt.Println(tree.query(3)) //查询arr[3]的值
	fmt.Println(tree.query(4)) //查询arr[4]的值
    fmt.Println(tree.query(0)) //查询arr[0]的值
}
/*
	树状数组操作(区间更新, 单点查询)
*/
type Tree struct {
	t []int
	length int
}
func build(arr []int) *Tree {
	length  := len(arr); arr2 := make([]int, length, length); arr2[0]=arr[0]
	for i:=1; i<length; i++ {arr2[i]= arr[i]-arr[i-1]}	//获取差分数组arr2
	tree := &Tree{make([]int, length+1), length+1}
	tree.init(arr2)	//用差分数组建立树状数组
	return tree
}
func (this *Tree)init(arr []int) {  //O(n)建树
	for i, j := 1, 0; i<this.length; i++ {
		this.t[i] += arr[i-1]
		j = i + lowBit(i); if j < this.length {this.t[j] += this.t[i]}
	}
}
func (this *Tree)upDate(l, r, v int) {this.up(l, v); this.up(r+1, -v)}
func (this *Tree)up(x, v int) {for x++; x < this.length; x+=lowBit(x) {this.t[x]+=v}}
func (this *Tree)query(v int) (ans int) {for v++; v>0; v -= lowBit(v) {ans+=this.t[v]}; return}
func lowBit(x int) int {return x&-x}